1. Field of the Invention
The present invention relates to texture compression techniques.
2. Background of the Invention
Compression and decompression intended to minimize the memory size needed to store 2D textures is a promising field of application for these techniques in the 3D graphic domain. This possible field of use is becoming more and more significant as the dimensions and number of these textures tend to increase in real applications. The level of detail tends to increase as required by some applications, such as 3D games, and, without the help of such techniques, memory size and bandwidth for access would tend to require increasing performance levels hardly sustainable in mobile, ultra low power, handheld systems. More to the point, these techniques are becoming increasingly important in wireless phone architectures with 3D games processing capabilities.
For example, assuming a texture dimension of 512×512 pixels 16 bit/color each and a depth of 3, the amount of memory needed is 1.5 M bytes. Assuming 20-30 frames per second, the memory bandwidth is 30 to 45 Mbytes/s.
Additional background information on this topic can be gathered from “Real-Time Rendering” by Tomas Akenine-Möller and Eric Haines, A.K. Peters Ltd, 2nd edition, ISBN 1568811829.
A well-known solution in this scenario was developed by the company S3; the related algorithm is designated S3TC (where TC stands for Texture Compression).
This has become a widely used de-facto standard and is included in the Microsoft DirectX libraries with adhoc API support.
Compression is performed off-line at system initialization and next the textures are stored in the main memory. Decompression processes act to decompress textures accessing the memory run-time when needed by the graphic engine. This means that only decompression is implemented in hardware form while compression is not.
Important parameters for the decompression engine are: steps needed to decompress textures and possible parallel operation; low latency between data-access-from-memory and data-out-from the decompression engine.
In order to better understand operation of the S3TC algorithm one may refer to an image in RGB format, where each color component R (Red) or G (Green) or B (Blue) is a sub-image composed by N pixels in the horizontal dimension and M pixels in vertical dimension. If each color component is coded with P bits, the number of bits per image is N*M*3*P.
For example, assuming N=M=256 and P=8, then the resulting size is 1,572,864 bits. If each sub-image R or G or B is decomposed in non-overlapping blocks of Q pixels in the horizontal dimension and S pixel in the vertical dimension, the number of blocks per sub-image is (N*M)/(Q*S) while per image is [3(NM/(Q*S)] and the number of bits per block is [3*(Q*S)]*P. If, for example Q=S=4 and P=8, then the resulting size of each block is 384 bits. If the number of bits per channel is R=5, G=6, B=5 then the resulting size of each block per image is (4*4)*(5+6+5)=256 bits. The S3TC algorithm is able to compress such an amount of data by 6 times when R=8, G=8, B=8 and 4 times when R=5, G=6, B=5. 64 bits compose the resulting compressed block always sent to decompression stage. This number is the results of the coding steps described below assuming Q=S=4.
To sum up, operation of the S3TC algorithm may be regarded as comprised of the following steps:
i) Decompose the R G B image in non-overlapped (Q=4)*(S=4) blocks of R G B colors
ii) Consider the following block composed by 16 pixels each one composed by R, G and B color components:
Pij=Rij U Gij U Bij (this denotes the pixel at the ij position the R G B image, and U is the union operator)
(R11 G11 B11)(R12 G12 B12)(R13 G13 B13)(R14 G14 B14)(R21 G21 B21)(R22 G22 B22)(R23 G23 B23)(R24 G24 B24)(R31 G31 B31)(R32 G32 B32)(R33 G33 B33)(R34 G34 B34)(R41 G41 B41)(R42 G42 B42)(R43 G43 B43)(R44 G44 B44)
iii) Decompose the block above in three sub-blocks called sub-block R, sub-block G and sub-block B as shown herein below, each block including only one color component:
R11R12R13R14sub-block RR21R22R23R24R31R32R33R34R41R42R43R44
G11G12G13G14sub-block GG21G22G23G24G31G32G33G34G41G42G43G44
B11B12B13B14sub-block BB21B22B23B24B31B32B33B34B41B42B43B44as shown in FIG. 1. Specifically, FIG. 1 shows RGB blocks ordered in different planes, with a RGB block shown on the left and a corresponding de-composition shown on the right.
iv) Sort in ascending order each sub-block color
v) Detect the black color, which is a pixel made of R=0 and G=0 and B=0
vi) If the black color is not detected, then set a color palette made by                a. 1st color is the minimum value of sub-block R (min_R), minimum value of sub-block G (min_G), minimum value of sub-block B (min_B).        b. 2nd color is the maximum value of sub-block R (max_R), maximum value of sub-block G (max_G), maximum value of sub-block B (max_B)        c. 3rd (Int1) is composed by (2*min R+max R)/3 (Int1R), (2*min G+max G)/3 (Int1G), (2*min B+max B)/3 (Int1B)        d. 4th (Int2) is composed by (min R+2*max R)/3 (Int2R), (min G+2*max G)/3 (Int2G), (min B+2*max B)/3 (Int2B)        
vii) Otherwise, if black color is detected then set a color palette made by                a. 1st color is minimum value of sub-block R (min_R), sub-block G (min_G), sub-block B (min_B) where each of them must not be equal to zero (the black color component) at the same time        b. 2nd color is maximum value of sub-block R (max_R), sub-block G (max_G), sub-block B (max_B)        c. 3rd (Int1) is composed by (min R+max R)/2 (Int1R), (min G+max G)/2 (Int1G), (min B+max B)/2 (Int1B)        d. 4th is the black color that has R,G,B components equal to zero        
viii) If black color is not detected define the look-up color palette as
                              Look          ⁢                      -                    ⁢          up          ⁢                                          ⁢          table                =                ⁢                  [                      Min_R            ,                                              Int1R        ,                            Int2R        ,                            Max_R        ]                                        ⁢                  [                      Min_G            ,                                              Int1G        ,                            Int2G        ,                            Max_G        ]                                        ⁢                  [                      Min_B            ,                                              Int1B        ,                            Int2B        ,                            Max_B        ]            
If black color is detected define the color palette as
                              Look          ⁢                      -                    ⁢          up          ⁢                                          ⁢          table                =                ⁢                  [                      MinR            ,                                              Int1R        ,                    MaxR                      0        ]                                        ⁢                  [                      MinG            ,                                              Int1G        ,                    MaxG                      0        ]                                        ⁢                  [                      MinB            ,                                              Int1B        ,                    MaxB                      0        ]            
ix) Associate the following 2 bits code (in boldface, under the palette) to each column of the above palette
                                          Look            ⁢                          -                        ⁢            up            ⁢                                                  ⁢            table                    =                    ⁢                      [                          MinR              ,                                                                      ⁢                      Int1R            ,                                                          ⁢                      Int2R            ,                                                          ⁢          MaxR          ]                                                        ⁢                      [                          MinG              ,                                                                      ⁢                      Int1G            ,                                                          ⁢                      Int2G            ,                                                          ⁢          MaxG          ]                                                        ⁢                      [                          MinB              ,                                                                      ⁢                      Int1B            ,                                                          ⁢                      Int2B            ,                                                          ⁢          MaxB          ]                                                        ⁢          00                                                ⁢          01                                                ⁢          10                                                ⁢          11                                                              Look            ⁢                          -                        ⁢            up            ⁢                                                  ⁢            table                    =                    ⁢                      [                          MinR              ,                                                                      ⁢                      Int1R            ,                                                          ⁢                      MaxR            ,                                                          ⁢          0          ]                                                        ⁢                      [                          MinG              ,                                                                      ⁢                      Int1G            ,                                                          ⁢                      MaxG            ,                                                          ⁢          0          ]                                                        ⁢                      [                          MinB              ,                                                                      ⁢                      Int1B            ,                                                          ⁢                      MaxB            ,                                                          ⁢          0          ]                                                        ⁢          00                                                ⁢          01                                                ⁢          10                                                ⁢          11                    
x) For each Pij=Rij U Gij U Bij (where i ranges from 1 to Q=4 and j ranges from 1 to S=4) compute the Euclidean distance Dist between it and each look-up color as defined above in vi.a,b,c,d or vii.a,b,c,d depending if black color has been detected or not. Essentially this is the Euclidean distance between two points in a three-dimensional coordinate space. Also, the difference is within a homologous color component (between R or G or B).Dist1=√(|Rij−MinR|2+|Gij−MinG|2+|Bij−MinB|2)Dist2=√(|Rij−Int1R|2+|Gij−Int1G|2+|Bij−Int1B|2)Dist3=√(|Rij−Int2R|2+|Gij−Int2G|2+|Bij−Int2B|2)Dist4=√(|Rij−MaxR|2+|Gij−MaxG|2+|Bij−MaxB|2)
xi) For each Pij=Rij U Gij U Bij find the minimum distance among Dist1, Dist2, Dist3 and Dist4. For example let it be Dist1.
xii) Send to a decoder process the code associated to the color enclosed in the look-up table that has the minimum distance. If it is Dist1 then the code is 00.
xiii) The decoder receives for each Q*S block as shown in FIG. 2                a. a two-bit code for each Pij that are addresses to the look-up table        b. MinR MinG MinB        c. MaxR MaxG MaxB        
xiv) If Min is received before Max by the decoder then black has been detected by the encoder otherwise not
xv) As shown in FIG. 2, the decoder operates as described in steps vi or vii depending on black color detection, computing                a. Int1R Int1G Int1Band Int2R Int2G Int2B if black color is not detected by encoder        otherwise        b. Int1R Int1G Int1B if black color is detected by encoder        
xvi) As shown in FIG. 2, the decoder addresses a look-up table with 2 bits code associated to each Pij and replaces it with the color stored in the look-up table color palette. Specifically ST, LUT, and CT indicate the source text, the look-up table, and the compressed text, respectively.
FIG. 3 shows how the data sent to the decoder are arranged in a bitstream and if the black color is not detected, while FIG. 4 shows the opposite case.
As stated before, the compression ratio is 6:1 or 4:1. This is because if colors are in R=8 G=8 B=8 format then 384 bits are coded with 64 (384/64=6) and if colors are in R=5 G=6 B=5 format then 256 bits are coded with 64 (256/64=4).
As shown in FIGS. 3 and 4, the sum of all the bits amounts to 64.